home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / lysrc.zip / LEXOPT.PAS < prev    next >
Pascal/Delphi Source File  |  1993-01-24  |  6KB  |  202 lines
  1.  
  2. unit LexOpt;
  3.  
  4. (* 2-5-91 AG *)
  5.  
  6. (* Copyright (c) 1990,91 by Albert Graef, Schillerstr. 18,
  7.    6509 Schornsheim/Germany
  8.    All rights reserved *)
  9.  
  10. interface
  11.  
  12. (* DFA optimization algorithm.
  13.    This is an efficient (O(n log(n)) DFA optimization procedure based on the
  14.    algorithm given in Aho/Sethi/Ullman, 1986, Section 3.9. *)
  15.  
  16. procedure optimizeDFATable;
  17.   (* optimize the state table *)
  18.  
  19. implementation
  20.  
  21. uses LexBase, LexTables;
  22.  
  23. (* Partition table used in DFA optimization: *)
  24.  
  25. const
  26.  
  27. max_parts = max_states;  (* number of partitions of equivalent states; at
  28.                             worst, each state may be in a partition by
  29.                             itself *)
  30.  
  31. type
  32.  
  33. PartTable      = array [0..max_states-1] of IntSetPtr;
  34.                    (* state partitions (DFA optimization) *)
  35.  
  36. StatePartTable = array [0..max_states-1] of Integer;
  37.                    (* partition number of states *)
  38.  
  39. var
  40.  
  41. (* partition table: *)
  42.  
  43. n_parts           : Integer;
  44. part_table        : ^PartTable;
  45. state_part        : ^StatePartTable;
  46.  
  47. (* optimized state and transition table: *)
  48.  
  49. n_opt_states      : Integer;
  50. n_opt_trans       : Integer;
  51. opt_state_table   : ^StateTable;
  52. opt_trans_table   : ^TransTable;
  53.  
  54.  
  55. function equivStates(i, j : Integer) : Boolean;
  56.   (* checks whether states i and j are equivalent; two states are considered
  57.      equivalent iff:
  58.      - they cover the same marker positions (/ and endmarkers of rules)
  59.      - they have transitions on the same symbols/characters, and corresponding
  60.        transitions go to states in the same partition
  61.      two different start states are never considered equivalent *)
  62.   var ii, jj, k : Integer;
  63.       mark_pos_i, mark_pos_j : IntSet;
  64.   begin
  65.     (* check for start states: *)
  66.     if (i<=2*n_start_states+1) and (j<=2*n_start_states+1) and
  67.        (i<>j) then
  68.       begin
  69.         equivStates := false;
  70.         exit;
  71.       end;
  72.     (* check end positions: *)
  73.     empty(mark_pos_i);
  74.     with state_table^[i] do
  75.       for k := 1 to size(state_pos^) do
  76.         if pos_table^[state_pos^[k]].pos_type=mark_pos then
  77.           include(mark_pos_i, state_pos^[k]);
  78.     empty(mark_pos_j);
  79.     with state_table^[j] do
  80.       for k := 1 to size(state_pos^) do
  81.         if pos_table^[state_pos^[k]].pos_type=mark_pos then
  82.           include(mark_pos_j, state_pos^[k]);
  83.     if not equal(mark_pos_i, mark_pos_j) then
  84.       begin
  85.         equivStates := false;
  86.         exit
  87.       end;
  88.     (* check transitions: *)
  89.     if n_state_trans(i)<>n_state_trans(j) then
  90.       equivStates := false
  91.     else
  92.       begin
  93.         ii := state_table^[i].trans_lo;
  94.         jj := state_table^[j].trans_lo;
  95.         for k := 0 to pred(n_state_trans(i)) do
  96.           if (trans_table^[ii+k].cc^<>trans_table^[jj+k].cc^) then
  97.             begin
  98.               equivStates := false;
  99.               exit
  100.             end
  101.           else if state_part^[trans_table^[ii+k].next_state]<>
  102.                   state_part^[trans_table^[jj+k].next_state] then
  103.             begin
  104.               equivStates := false;
  105.               exit
  106.             end;
  107.         equivStates := true;
  108.       end
  109.   end(*equivStates*);
  110.  
  111. procedure optimizeDFATable;
  112.  
  113.   var
  114.     i, ii, j : Integer;
  115.     act_part, new_part, n_new_parts : Integer;
  116.  
  117.   begin
  118.  
  119.     n_parts := 0;
  120.  
  121.     (* Initially, create one partition containing ALL states: *)
  122.  
  123.     n_parts := 1;
  124.     part_table^[0] := newIntSet;
  125.     for i := 0 to n_states-1 do
  126.       begin
  127.     include(part_table^[0]^, i);
  128.     state_part^[i] := 0;
  129.       end;
  130.  
  131.     (* Now, repeatedly pass over the created partitions, breaking up
  132.        partitions if they contain nonequivalent states, until no more
  133.        partitions have been added during the last pass: *)
  134.  
  135.     repeat
  136.       n_new_parts := 0; act_part := 0;
  137.       new_part := n_parts;
  138.       part_table^[new_part] := newIntSet;
  139.       while (n_parts<n_states) and (act_part<n_parts) do
  140.         begin
  141.           for i := 2 to size(part_table^[act_part]^) do
  142.             if not equivStates(part_table^[act_part]^[1],
  143.                                part_table^[act_part]^[i]) then
  144.               (* add to new partition: *)
  145.               include(part_table^[new_part]^, part_table^[act_part]^[i]);
  146.           if size(part_table^[new_part]^)<>0 then
  147.             begin
  148.               (* add new partition: *)
  149.               inc(n_parts); inc(n_new_parts);
  150.               (* remove new partition from old one: *)
  151.               setminus(part_table^[act_part]^, part_table^[new_part]^);
  152.               (* update partition assignments: *)
  153.               for i := 1 to size(part_table^[new_part]^) do
  154.                 state_part^[part_table^[new_part]^[i]] := new_part;
  155.               inc(new_part);
  156.               part_table^[new_part] := newIntSet;
  157.             end;
  158.           inc(act_part);
  159.         end;
  160.     until n_new_parts=0;
  161.  
  162.     (* build the optimized state table: *)
  163.  
  164.     n_opt_states := n_parts;
  165.     n_opt_trans := 0;
  166.     for i := 0 to n_parts-1 do
  167.       begin
  168.         ii := part_table^[i]^[1];
  169.         opt_state_table^[i] := state_table^[ii];
  170.         with opt_state_table^[i] do
  171.           begin
  172.             trans_lo := n_opt_trans+1;
  173.             trans_hi := n_opt_trans+1+state_table^[ii].trans_hi-
  174.                         state_table^[ii].trans_lo;
  175.             for j := 2 to size(part_table^[i]^) do
  176.               setunion(state_pos^, state_table^[
  177.                                      part_table^[i]^[j]].state_pos^);
  178.           end;
  179.         for j := state_table^[ii].trans_lo to state_table^[ii].trans_hi do
  180.           begin
  181.             inc(n_opt_trans);
  182.             opt_trans_table^[n_opt_trans] := trans_table^[j];
  183.             with opt_trans_table^[n_opt_trans] do
  184.               next_state := state_part^[next_state];
  185.           end;
  186.       end;
  187.  
  188.       (* update state table: *)
  189.  
  190.       n_states     := n_opt_states;
  191.       n_trans      := n_opt_trans;
  192.       state_table^ := opt_state_table^;
  193.       trans_table^ := opt_trans_table^;
  194.  
  195.   end(*optimizeDFATable*);
  196.  
  197. begin
  198.   new(part_table);
  199.   new(state_part);
  200.   new(opt_state_table);
  201.   new(opt_trans_table);
  202. end(*LexOpt*).